import java.io.*;
import java.util.*;


public class ACETokSentence {

  int m_nSent;

  String[] m_vecTokens;
  String[] m_vecPOS;

  // word-word dependencies, stored as adjacency lists
  LinkedList[] m_vecDeps;

  LinkedList m_lstEM;
  LinkedList m_lstRM;
  
  public ACETokSentence(int nSent, Vector vecTokens, Vector vecPOS)
  {
    m_nSent = nSent;

    m_vecTokens = (String[]) vecTokens.toArray(new String[0]);
    m_vecPOS = (String[]) vecPOS.toArray(new String[0]);

    m_vecDeps = new LinkedList[m_vecTokens.length];
    for (int i = 0; i < m_vecDeps.length; i++)
      m_vecDeps[i] = new LinkedList();

    m_lstEM = new LinkedList();
    m_lstRM = new LinkedList();
  }


  public void readDependencies(String strParse)
  {
    // no dependencies for the unparsed sentence
    if (strParse.indexOf("~") == -1)
      return;

    // extract dependencies from the parsed sentence
    StringTokenizer st = new StringTokenizer(strParse);
    int nTok[] = new int[1];
    nTok[0] = 0;
    readDeps(st, nTok);
  }

  public int readDeps(StringTokenizer st, int nTok[])
  {
    String strNode = st.nextToken();
    //    System.out.println(strNode);
    if (strNode.indexOf('~') != -1) {
      StringTokenizer stNode = new StringTokenizer(strNode.substring(1), "~");
      // ignore POS tag
      stNode.nextToken();
      // ignore word
      stNode.nextToken();

      int nChildren = Integer.parseInt(stNode.nextToken());
      int nHead = Integer.parseInt(stNode.nextToken()) - 1;

      int[] children = new int[nChildren];
      for (int i = 0; i < nChildren; i++) {
	children[i] = readDeps(st, nTok);
	while (children[i] == -1)
	  children[i] = readDeps(st, nTok);
      }

      // ignore ")"
      String strClose = st.nextToken();
      while (strClose.indexOf("/PUNC") != -1) {
	nTok[0]++;
	strClose = st.nextToken();
      }
      assert strClose.equals(")") : strClose;

      // add dependencies
      for (int i = 0; i < nHead; i++)
	m_vecDeps[children[i]].add(new Integer(children[nHead]));
      for (int i = nHead + 1; i < nChildren; i++)
	m_vecDeps[children[i]].add(new Integer(children[nHead]));

      return children[nHead];
    }
    else {
      int nPos = strNode.indexOf("/PUNC");
      if (nPos == -1) 
	return nTok[0]++;
      else {
	nTok[0]++;
	return -1;
      }
    }
  }


  public int[] getShortestPath(int e1, int e2)
  {
    LinkedList[] vecDeps = getUndirectedDeps();

    int precedent[] = new int[m_vecTokens.length];
    Arrays.fill(precedent, -1);
    precedent[e1] = m_vecTokens.length;

    LinkedList lstFrontier = new LinkedList();
    lstFrontier.add(new Integer(e1));
    
    Integer crt = (Integer) lstFrontier.removeFirst();
    while (crt != null) {
      int nCrt = crt.intValue();
      if (nCrt == e2)
	break;

      ListIterator it = vecDeps[nCrt].listIterator();
      while (it.hasNext()) {
	Integer elem = (Integer) it.next();
	int nElem = elem.intValue();
	if (precedent[nElem] == -1) {
	  lstFrontier.add(elem);
	  precedent[nElem] = nCrt;
	}
      }

      if (lstFrontier.size() == 0)
	crt = null;
      else
	crt = (Integer) lstFrontier.removeFirst();
    }

    int[] path;
    if (precedent[e2] == -1)
      return null;
    else {
      LinkedList lstPath = new LinkedList();
      int nCrt = e2;
      while (nCrt != m_vecTokens.length) {
	lstPath.addFirst(new Integer(nCrt));
	nCrt = precedent[nCrt];
      }
      path = new int[lstPath.size()];
      ListIterator it = lstPath.listIterator();
      int i = 0;
      while (it.hasNext()) {
	Integer intElem = (Integer) it.next();
	path[i++] = intElem.intValue();
      }
    }

    return path;
  }


  public LinkedList[] getUndirectedDeps()
  {
    LinkedList[] vecDeps = new LinkedList[m_vecDeps.length];
    for (int i = 0; i < vecDeps.length; i++)
      vecDeps[i] = new LinkedList(m_vecDeps[i]);
    
    for (int i = 0; i < vecDeps.length; i++) {
      ListIterator it = m_vecDeps[i].listIterator();
      while (it.hasNext()) {
	Integer crt = (Integer) it.next();
	int j = crt.intValue();
	vecDeps[j].add(new Integer(i));
      }
    }

    return vecDeps;
  }


  public int[] getShortPath(int e1, int e2)
  {
    boolean[] bPath = new boolean[e2 - e1 + 1];
    Arrays.fill(bPath, true);

    ListIterator it = m_lstEM.listIterator();
    while (it.hasNext()) {
      ACEEMention em = (ACEEMention) it.next();
      if (em.m_nBeg > e1 && em.m_nBeg + em.m_nLen <= e2 &&
	  bPath[em.m_nHBeg + em.m_nHLen - 1 - e1]) {
	for (int i = em.m_nBeg; i < em.m_nBeg + em.m_nLen; i++)
	  bPath[i - e1] = false;
	bPath[em.m_nHBeg + em.m_nHLen - 1 - e1] = true;
      }
      else if (em.m_nHBeg > e1 && em.m_nHBeg + em.m_nHLen <= e2 &&
	  bPath[em.m_nHBeg + em.m_nHLen - 1 - e1]) {
	for (int i = em.m_nHBeg; i < em.m_nHBeg + em.m_nHLen; i++)
	  bPath[i - e1] = false;
	bPath[em.m_nHBeg + em.m_nHLen - 1 - e1] = true;
      }
      else if (e1 == em.m_nHBeg + em.m_nHLen - 1) {
	for (int i = em.m_nBeg; i < em.m_nBeg + em.m_nLen; i++)
	  if (i > e1 && i < e2)
	    bPath[i - e1] = false;
      }
      else if (e2 == em.m_nHBeg + em.m_nHLen - 1) {
	for (int i = em.m_nBeg; i < em.m_nBeg + em.m_nLen; i++)
	  if (i > e1 && i < e2)
	    bPath[i - e1] = false;
      }
    }

    // count head positions
    int nLen = 0;
    for (int i = 0; i < bPath.length; i++)
      if (bPath[i])
	nLen++;

    // include head positions in path
    int[] path = new int[nLen];
    nLen = 0;
    for (int i = 0; i < bPath.length; i++)
      if (bPath[i])
	path[nLen++] = i + e1;

    return path;
  }


  public int length()
  {
    return m_vecTokens.length;
  }


  public void addEMention(ACEEMention aceEM)
  {
    m_lstEM.add(aceEM);
  }

  public void addRMention(ACERMention aceRM)
  {
    m_lstRM.add(aceRM);
  }

  public void displayRM()
  {
    ListIterator it = m_lstRM.listIterator();
    while (it.hasNext()) {
      ACERMention aceRM = (ACERMention) it.next();
      String strArg1 = getEMText(aceRM.m_arg1);
      String strArg2 = getEMText(aceRM.m_arg2);

      System.out.println(m_nSent + ": " + aceRM.m_relation.m_bExplicit 
			 + ": (" + aceRM.m_relation.m_strType 
			 + ", " + aceRM.m_relation.m_strSType + ") "
			 + strArg1 + " --> " + strArg2
			 + ": " + aceRM.m_arg1.m_strType + " "
			 + aceRM.m_arg1.m_entity.m_strType + " "
			 + aceRM.m_arg2.m_strType + " "
			 + aceRM.m_arg2.m_entity.m_strType);
    }
  }

  public String getEMText(ACEEMention aceEM)
  {
    String strText = "";
    for (int i = aceEM.m_nHBeg; i < aceEM.m_nHBeg + aceEM.m_nHLen; i++)
      strText += m_vecTokens[i] + " ";

    return strText.trim();
  }

  public void displayDeps()
  {
    for (int i = 0; i < m_vecDeps.length; i++)
      if (m_vecDeps[i].size() > 0) {
	ListIterator it = m_vecDeps[i].listIterator();
	while (it.hasNext()) {
	  Integer intHead = (Integer) it.next();
	  int j = intHead.intValue();
	  System.out.println(m_vecTokens[i] + " --> " + m_vecTokens[j]);
	}
      }
  }

}
